package algorithm.leetcode.medium;

/*
 给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。
 */

import java.util.ArrayList;
import java.util.List;

/**
 * @author jack.wu
 * @version 1.0
 * @date 2020/12/18
 */
public class Question230 {

    public static void main(String[] args) {

    }

    /**
     * 思路：根据二叉搜索树的性质 使用中序遍历
     */
    public int kthSmallest(TreeNode root, int k) {
        List<Integer> perValList = new ArrayList<>(10);
        helper(root, perValList);
        return perValList.get(k - 1);
    }

    private void helper(TreeNode root, List<Integer> perValList) {
        if (root == null) {
            return;
        }
        helper(root.left, perValList);
        perValList.add(root.val);
        helper(root.right, perValList);
    }

    private static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
